package com.peng.leetcode.backtracking;

/**
 * Exist
 *
 * @author: lupeng6
 * @create: 2020/12/28 21:21
 */
public class Exist {

    public static void main(String[] args) {
//        char[][] board = {{'A'}};

        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABCCED";

//        System.out.println(new Exist().exist(board, "A"));
        System.out.println(new Exist().exist(board, word));
    }


    private boolean isExist = false;

    private boolean[][] marked;

    private char[][] board;

    private int xLength;

    private int yLength;

    private int wordLength;

    private String word;

    private int[][] operations = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.xLength = board.length;
        this.yLength = board[0].length;
        this.wordLength = word.length();
        this.marked = new boolean[xLength][yLength];
        this.word = word;
        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            for (int j = 0; j < chars.length; j++) {
                dfs(0, i, j);
            }
        }
        return isExist;
    }

    public void dfs(int strIndex, int x, int y) {
        if (strIndex >= wordLength) {
            isExist = true;
            return;
        }
        if (isExist) {
            return;
        }
        if (board[x][y] == word.charAt(strIndex)) {
            if (strIndex + 1 == wordLength) {
                isExist = true;
                return;
            }

            marked[x][y] = true;
            for (int[] operation : operations) {
                int newX = x + operation[0];
                int newY = y + operation[1];
                if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length && !marked[newX][newY]) {
                    dfs(strIndex + 1, newX, newY);
                    if (isExist) {
                        return;
                    }
                }
            }
            marked[x][y] = false;
        }
    }
}
